//
// Created by Joy on 2024/7/24.
//

#include <bits/stdc++.h>

using namespace std;

typedef struct BiNode{
    char data;
    struct BiNode *left, * right;
}BiNode,*BiTree;
bool CreateBiTree(BiTree &T){
    char ch;
    cin >> ch;
    if (ch == '#') T = NULL;
    else{
        T = new BiNode;
        T->data = ch;
        CreateBiTree(T->left);
        CreateBiTree(T->right);
    }
    return true;
}
void Pre(BiTree T){
    if (T == NULL) return;
    cout << T->data;
    Pre(T->left);
    Pre(T->right);
}
void In(BiTree T){
    if (T == NULL) return;
    Pre(T->left);
    cout << T->data;
    Pre(T->right);
}
void Pos(BiTree T){
    if (T == NULL) return;
    Pre(T->left);
    Pre(T->right);
    cout << T->data;
}
/*
//先序非递归遍历二叉树
void InOrderTraverse(BiTree BT){
    BiTree T = BT;
    Stack S = CreateStack(MaxSize); //创建栈
    while (T || IsEmpty(S)){
        while (T){
            Push(S,T);
            T = T->left;
        }
        if (!IsEmpty(S)){
            T = Pop(S);
            cout << T->data;
            T = T->right;
        }
    }
}*/


int main() {
    BiNode *t;
    CreateBiTree(t); //ABC##DE#G##F###
    Pre(t);
    printf("\n");
    In(t);
    cout << endl;
    Pos(t);
}

